
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package edu.yonsei.iwb.smarttv.querygraph.algorithm;

import com.hp.hpl.jena.rdf.model.Model;
import com.hp.hpl.jena.rdf.model.Property;
import com.hp.hpl.jena.rdf.model.Resource;
import edu.yonsei.iwb.smarttv.model.*;
import edu.yonsei.iwb.smarttv.util.SMARTTVLog;
import java.util.*;

/**
 *
 * @author DK
 */
public class AStarAlgorithm {

    private SMARTTVModel tvModel;
//    private Model model;
    private MatrixModel mm;
    private Hashtable<Resource, Integer> nodeInfo;
    private Vector<MNode> nodes;
    private MArcSet[][] arcMatrix;    
    private int LOOP_THRESHOLD = 600;
    private int FRINGE_DEPTH = 10;
    private Resource TARGETRESOURCE;

    public AStarAlgorithm(SMARTTVModel tvModel) {
        this.tvModel = tvModel;
//        this.model = this.tvModel.getJenaModel();
        this.mm = this.tvModel.getMatrixModel();
        this.nodes = this.mm.getNodeSet();
        this.nodeInfo = this.mm.getNodeIDTable();
        this.arcMatrix = this.mm.getArcMatrix();
    }

    public Vector<ShortestPathSet> getShortestPathVector(ConceptualGraph conceptualGraph) {
        Hashtable<ConceptArc, Vector<ShortestPath>> pathCombinationSet = new Hashtable<ConceptArc, Vector<ShortestPath>>();

        for (int i = 0; i < conceptualGraph.size(); i++) {
            ConceptArc ca = conceptualGraph.get(i);

            if (ca.getArcType() == ArcType.LITERAL_TYPE) {
                // Concept Arc가 Literal type 일 경우
                ShortestPath path = new ShortestPath();
                MNode literalNode = new MNode(ca.getHead().getNode(), nodes.size() - 1, NodeType.LITERAL_TYPE, false);
                MNode resourceNode = nodes.get(nodeInfo.get(ca.getTail().getNode()));
                Vector<ShortestPath> pathSet = new Vector<ShortestPath>();
                path.add(new MArc(literalNode, resourceNode, null, 0, true));
                pathSet.add(path);
                pathCombinationSet.put(ca, pathSet);
            } else {
                
                MNode source = nodes.get(nodeInfo.get(ca.getHead().getNode()));
                MNode target = nodes.get(nodeInfo.get(ca.getTail().getNode()));

                Vector<ShortestPath> arcSet = this.findShortestPathSet(source, target, ca.getProperty());
                if (!arcSet.isEmpty()) {
                    pathCombinationSet.put(ca, arcSet);
                } else {
                    SMARTTVLog.log(SMARTTVLog.DETAIL, " ::Shortest path between '"+source.getNode().getLocalName()+"' and '"+target.getNode().getLocalName()+"' is not exist::\n");
                }
                
            }
        }

        Vector<ShortestPathSet> spvSet = this.generateMultiPathCombinationSet(pathCombinationSet);
        return spvSet;
    }

    public Vector<ShortestPath> findShortestPathSet(MNode source, MNode target, Vector<Property> pattern) {
        Vector<ShortestPath> resultPathSet = new Vector<ShortestPath>();
        
        int loop = 0;
        int depth =0;
        int sourceID = source.getId();
        int targetID = target.getId();

        Vector<ShortestPath> fringeSet = new Vector<ShortestPath>();

        // generate initial fringe set
        for (int i = 0; i < this.arcMatrix[sourceID].length; i++) {            
            MArcSet candidateArcSet = this.arcMatrix[sourceID][i];            
            for (int j = 0; j < candidateArcSet.size(); j++) {                
                MArc arc = candidateArcSet.get(j);
                ShortestPath sp = new ShortestPath();
                sp.add(arc);
                fringeSet.add(sp);
            }
        }
                
        while (true) {            
            // check search limits
            if(loop > this.LOOP_THRESHOLD){
//                System.out.println("***************************** 루프 제한 통과 ***********************************");
                return resultPathSet;
            }else if(depth > this.FRINGE_DEPTH){
//                System.out.println("***************************** 깊이 제한 통과 ***********************************");
                return resultPathSet;
            }else if(fringeSet.isEmpty()){
//                System.out.println("***************************** 더이상 대안 없음 ***********************************");
                return resultPathSet;
            }
//            System.out.println("--------------------- "+loop+" 번째 Loop 시작 --------------------------\n");
            ShortestPath minsp = this.getMininmumFringe(fringeSet);
//            System.out.println("가장 짧은 패스 : " + minsp.toString()); // 이거 불르때마다 웨이트 계산하지말고, 있으면 계산안하기..
            depth = minsp.size();
            if (this.checkTargetPath(minsp, targetID, pattern)) {
//                System.out.println("이 패스가 정답임");
                resultPathSet.add(minsp);
                if (resultPathSet.size() == SMARTTVModel.NUMBER_OF_PATH) {
                    break;
                } else {
                    loop++;
//                    System.out.println("현재 찾은 패스의 개수  " + resultPathSet.size() +"  /   " + (SMARTTVModel.NUMBER_OF_PATH - resultPathSet.size()) +" 개 남음");
                    fringeSet.remove(minsp);
//                    this.updateFringeSetByMinPath(minsp, fringeSet);                    
                }
            } else {                
                loop++;
                this.updateFringeSetByMinPath(minsp, fringeSet);
            }
            
//            System.out.println("\n--------------------- "+ (loop-1) +" 번째 Loop 끝 --------------------------");
                                   
        }
        return resultPathSet;
    }

    /**
     * fringe set update
     *
     * @param msp
     * @param fringeSet
     * @return
     */
    private void updateFringeSetByMinPath(ShortestPath msp, Vector<ShortestPath> fringeSet) {

        MArc lastArcOfPath = msp.lastElement();
        int tailnodeID = lastArcOfPath.getTailNode().getId();
//        System.out.println("꼬리와 연결된 아크들");
        for (int i = 0; i < this.arcMatrix[tailnodeID].length; i++) {
            MArcSet cndMArcSet = this.arcMatrix[tailnodeID][i];            
            for (int j = 0; j < cndMArcSet.size(); j++) {
                MArc arc = cndMArcSet.get(j);                
                if(!checkRedundantArc(msp, arc)){
//                    System.out.println(arc.toString());
                    ShortestPath sp = new ShortestPath();
                    for (int k = 0; k < msp.size(); k++) {
                        sp.add(msp.get(k));
                    }
                    sp.add(arc);
                    fringeSet.add(sp);
                }
            }
        }

        fringeSet.remove(msp);        
    }
    
    private boolean checkRedundantArc(ShortestPath sp, MArc arc2){
        
        boolean result = false;
        
        for (int i = 0; i < sp.size(); i++) {
            MArc arc1 = sp.get(i);
            if(arc1.getProperty() == arc2.getProperty()){            
                if(arc1.getDirection() == arc2.getDirection()){
                    if(arc1.getHeadNode().getId() == arc2.getHeadNode().getId()){
                        if(arc1.getTailNode().getId() == arc2.getTailNode().getId()){                            
                            return true;
                        }
                    }
                }else{
                    if(arc1.getHeadNode().getId() == arc2.getTailNode().getId()){
                        if(arc1.getTailNode().getId() == arc2.getHeadNode().getId()){
                            
                            return true;
                        }
                    }
                }            
            }
        }
        
        return result;        
        
    }

    /**
     * Fringe에서 가장 짧은 Arc 반환
     *
     * @param spset
     * @return
     */
    private ShortestPath getMininmumFringe(Vector<ShortestPath> spset) {

        double ws = Double.POSITIVE_INFINITY;
        ShortestPath result = null;
        for (int i = 0; i < spset.size(); i++) {
            ShortestPath sp = spset.get(i);
            if (sp.getPathScore() < ws) {
                ws = sp.getPathScore();
                result = sp;
            }
        }

        return result;
    }

    /**
     * check the minimum path is satisfied target conditions
     *
     * @param msp
     * @param targetID
     * @param pattern
     * @return
     */
    private boolean checkTargetPath(ShortestPath msp, int targetID, Vector<Property> pattern) {
//        System.out.println("====    " + msp.toString());
        if(msp != null){
            int lastnodeID = msp.lastElement().getTailNode().getId();
//            System.out.println("lastnode =  " + msp.lastElement().getTailNode());
            if (lastnodeID == targetID) {
//                System.out.println("마지막 노드가 타겟과 같음");
                if (pattern.isEmpty()) {
                    // patten is not exist                
                    return true;
                } else {
                    // pattern is exist                
//                    System.out.println("Pattern 이 존재함");
                    Vector<Property> propertyOfPath = msp.getAllPropertySet();

                    if (propertyOfPath.containsAll(pattern)) {
                        // check order of property set of path based on the pattern 
                        boolean result = true;
                        int index = -1;
                        for (int i = 0; i < pattern.size(); i++) {
                            Property p = pattern.get(i);
                            if (index < propertyOfPath.indexOf(p)) {
                                index = propertyOfPath.indexOf(p);
                            } else {
                                result = false;
                                break;
                            }
                        }
                        
                        if(result){
//                            System.out.println("순서에 맞게 패턴 존재");
                        }else{
//                            System.out.println("패턴이 순서에 맞지 않음");
                        }                        
                        
                        return result;

                    } else {
//                        System.out.println("패스에 패턴 존재 안함");
                        return false;
                    }
                }
            } else {
//                System.out.println("타겟과 다름.");
                return false;
            }
        }else{
            return false;
        }
    }

    /**
     * Generate combination set of the case that multi path are found from astar
     *
     * @param pcomb Hashtable of that concept arc as a key and the set of
     * shortest path as a value
     * @param spv
     * @return
     */
    private Vector<ShortestPathSet> generateMultiPathCombinationSet(Hashtable<ConceptArc, Vector<ShortestPath>> pcomb) {
        Vector<ShortestPathSet> spvSet = new Vector<ShortestPathSet>();

        Enumeration<ConceptArc> e = pcomb.keys();
        while (e.hasMoreElements()) {
            ConceptArc ca = e.nextElement();
            Vector<ShortestPath> spSet = pcomb.get(ca);
            Vector<ShortestPathSet> tmpset = new Vector<ShortestPathSet>();

            for (int i = 0; i < spSet.size(); i++) {
                ShortestPathSet newspv = new ShortestPathSet();
                newspv.put(ca, spSet.get(i));
                tmpset.add(newspv);
            }
            this.updateSPVSet(spvSet, tmpset);
        }

//        System.out.println(" Multi Path로 발생한 SPV의 갯수 = " + spvSet.size());

        return spvSet;
    }

    private void updateSPVSet(Vector<ShortestPathSet> spvSet, Vector<ShortestPathSet> tmpset) {

        if (spvSet.isEmpty()) {
            for (int j = 0; j < tmpset.size(); j++) {
                ShortestPathSet tmpspv = tmpset.get(j);
                spvSet.add(tmpspv);
            }
        } else {
            Vector<ShortestPathSet> newSPVSet = new Vector<ShortestPathSet>();
            for (int i = 0; i < spvSet.size(); i++) {
                ShortestPathSet spv = spvSet.get(i);
                for (int j = 0; j < tmpset.size(); j++) {
                    ShortestPathSet tmpspv = tmpset.get(j);
                    ShortestPathSet newspv = new ShortestPathSet();
                    newspv.updateShortestPath(spv);
                    newspv.updateShortestPath(tmpspv);
                    newSPVSet.add(newspv);
                }
            }

            spvSet.clear();
            spvSet.addAll(newSPVSet);
        }
    }
}
